package com.li.sort.arithmetic;

import java.util.Arrays;
import java.util.Random;

public class InsertSort {
	public static final int SIZE = 10000;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		long time1= System.currentTimeMillis();
		System.out.println(Arrays.toString(array));
		insertSort(array);
		System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}
	
	/**
	 * n-1趟就ok
	 * @param array
	 */
	public static void insertSort(int[] array){
		for(int i = 1;i < array.length;i++){
			int temp = array[i];
			int j = i-1;
			for( ;j >= 0;j--){
				if(temp < array[j]){
					array[j+1] = array[j];
				}else{
					break;
				}
			}
			array[j+1] = temp;
		}
	}
}
